import java.util.Arrays;

public class test {
    //插入排序
    public static void simpleSort(int[] arr){
        for(int i = 1; i < arr.length; i++){
            int tmp = arr[i];
            int j = i-1;
            for(; j >=0; j--){
                if(arr[j] > tmp){
                    arr[j+1] = arr[j];
                }
                else{
                    arr[j+1] = tmp;
                    break;
                }
            }
            arr[j+1] = tmp;
        }
    }
    //希尔排序
    public static void ShellSort(int[] arr){
        int gap = arr.length;
        while(gap > 1){
            gap /= 2;
            Shell(arr, gap);
        }
    }
    public static void Shell(int[] arr, int gap){
        for(int i = gap; i < arr.length; i++){
            int j = i - gap;
            int tmp = arr[i];
            for(; j >= 0; j-=gap){
                if(arr[j] > tmp){
                    arr[j+gap] = arr[j];
                }
                else{
                    arr[j+gap] = tmp;
                    break;
                }
            }
            arr[j+gap] = tmp;
        }
    }
    public static void main(String[] args) {
        int[] arr = {1,5,2,9,7,10,3};
        ShellSort(arr);
        //simpleSort(arr);
        System.out.println((String) Arrays.toString(arr));
    }
}